package l.l.w.CodingInterviews;

import java.util.Arrays;
import java.util.Stack;

/**
 * Created by llw on 2018/3/20/0020.
 */
public class 二叉搜索树的后序遍历序列 {

    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0) return false;

        return judge(sequence,0,sequence.length-1);

    }

    private boolean judge(int[] sequence, int start,int end) {
        if(start >= end) return true;
        int mid = sequence[end];
        int i = 0;
        while(sequence[i++] < mid && i<end);
        int j = i-1;
        for(;i < end; ++i){
            if(sequence[i] < mid) return  false;
        }
        return  judge(sequence,start,j) && judge(sequence,j+1,end-1);
    }

    /**
     * 麻烦！！！
     * 排序之后得到 中序遍历的结果
     * 然后重构二叉树
     * @param sequence
     * @return
     */
    public boolean VerifySquenceOfBST1(int [] sequence) {
        if(sequence == null || sequence.length == 0) return false;
        int len = sequence.length;
        int[] inOrder = new int[len];
        for(int i = 0; i < len; ++i){
            inOrder[i] = sequence[i];
        }
        Arrays.sort(inOrder);

        return isSat(sequence,0,len-1,inOrder,0,len-1);
    }
    private boolean isSat(int[] pos,int pstart,int pend, int[] in, int istart,int iend){
        if( pend - pstart != iend -istart){

            return false;
        }
        if(pstart > pend || istart > iend){
            return true;
        }
        if(pstart == pend){
            if(pos[pstart] == in[istart])
                return true;
            else return false;
        }
        int root = pos[pend];
        int index = findIndex(in,root);

        return isSat(pos,pstart,pstart+(index - istart-1),in,istart,index-1) && isSat(pos,pend-(iend-index),pend-1,in,index+1,iend);
    }
    private int findIndex(int[] pos,int root){
        for(int i = 0; i < pos.length; ++i){
            if(pos[i] == root) return i;
        }
        return -1;
    }
    public static void main(String[] args) {
        int[] a = {4,6,7,5};
        System.out.println(new 二叉搜索树的后序遍历序列().VerifySquenceOfBST(a));
    }
}
